#include <stdio.h>
#include <stdlib.h>

// 自定义栈结构
typedef struct{
  int *data; // 指向动态数组
  size_t size; // 栈内有效元素个数
  size_t capacity; // 动态数组的容量
} Stack;

/**
 * @brief 初始化栈
 * @param stack 指向栈的指针
 * @param capacity 栈空间大小
 * @return 无
 */
void initStack(Stack *stack, size_t capacity){
  // 为底层数组分配空间
  stack->data = (int *)malloc(capacity*sizeof(int));
  stack->size=0;
  stack->capacity=capacity;
}

/**
 * @brief 获取栈内有效元素的个数
 * @param stack 指向栈的指针
 * @return 无
 */
size_t getSize(const Stack *stack){
  return stack->size;
}

/**
 * @brief 新元素入栈
 * @param stack 栈的指针
 * @param element 新元素值
 * @return 无
 */
void push(Stack *stack, int element){
  // 判断是否栈满
  if(stack->size==stack->capacity){
    // 扩容至两倍
    stack->capacity *=2;
    stack->data = (int *)realloc(stack->data,stack->capacity*sizeof(int));
  }
  // 将元素压入栈顶
  stack->data[stack->size] = element;
  stack->size++; // 更新有效元素的个数
}

/**
 * @brief 元素出栈
 * @param stack 栈的指针
 * @return 出栈元素的值
 */
int pop(Stack *stack){
  if(stack->size==0){
    printf("栈已经空了");
    return -1;
  }
  stack->size--;
  return stack->data[stack->size];
}

/**
 * @brief 释放栈内存
 * @param stack 栈的指针
 * @return 无
 */
void destroyStack(Stack *stack){
  free(stack->data); // 释放堆区的数组
  stack->data=NULL; // 防止野指针
  stack->size=0;
  stack->capacity=0;
}

int main(void){
  Stack stack;
  initStack(&stack,2); // 初始化栈
  push(&stack,1); // 入栈
  push(&stack,2);
  printf("size:%zu\n",getSize(&stack));
  printf("弹出的栈顶元素:%d\n",pop(&stack));
  printf("弹出的栈顶元素:%d\n",pop(&stack));
  printf("弹出的栈顶元素:%d\n",pop(&stack));
  destroyStack(&stack);
  return 0;
}
